The invention relates to a multi-port bridge for a local area network. More particularly, the invention relates to a technique for statistically reducing a number of learning operations required to be performed for updating a look-up table utilized for directing data packets through a multi-port bridge a local are network.
Nodes of a local area network (LAN) are typically interconnected by a shared transmission medium. The amount of data traffic that the shared transmission medium can accommodate, however, is limited. For example, only one node at a time can successfully transmit data to another node over the shared transmission medium. If two or more nodes simultaneously attempt to transmit data, a data collision-occurs, which tends to corrupt the data being transmitted. Thus, nodes that share a transmission medium are considered to be in a same collision domain.
A multi-port bridge allows simultaneous communication between nodes of the LAN by segmenting the LAN into multiple collision domains (also referred to as network segments or LAN segments), each segment having a corresponding transmission medium.
FIG. 1 illustrates a conventional local area network including a multi-port bridge 10.
The multi-port bridge 10 has eight ports A-H, though the number of ports can vary. Each port A-H is connected to a segment 11-18 of the LAN. Each segment 11-18 typically includes one or more nodes 19-34, such as a workstation, a personal computer, a data terminal, a file server, a printer, a facsimile, a scanner or other conventional digital device. Each of the nodes 19-34 has an associated node address (also referred to as a medium access control (MAC) address) which uniquely identifies the node. The nodes 19-34 are configured to send data, one to another, in the form of discrete data packets.
When the LAN operates according to Ethernet standards, such as the Institute of Electrical and Electronics Engineers (IEEE) 802.3 standard, data is communicated in the form of discrete packets. FIG. 2 illustrates a conventional IEEE 802.3 data packet 40. The data packet 40 includes an eight byte long pre-amble 41 which is generally utilized for synchronizing a receiver to the data packet 40. The pre-amble 41 includes seven bytes of pre-amble and one byte of start-of-frame. Following the pre-amble 41, the data packet 40 includes a six-byte-long destination address 42, which is the node address of a node which is an intended recipient for the data packet 40. Next, the data packet 40 includes a six-byte-long source address 43, which is the node address of a node which originated the data packet 40. Following the source address 43 is a two-byte length field 44. Following the length field 44 is a data field 45. The data field 45 can be up to 1500 bytes long. Finally, the data packet 40 includes a two-byte frame check field 46 which allows a recipient of the data packet 40 to determine whether an error has occurred during transmission of the data packet 40.
When a node (source node) sends data to another node (destination node) located on its same segment of the LAN (intra-segment communication), the data is communicated directly between the nodes without intervention by the multi-port bridge 10 and is known as an intra-segment packet. Therefore, when the multi-port bridge 10 receives an intra-segment packet, the multi-port bridge 10 does not bridge the packet (the packet is filtered). When a node (source node) sends a data packet to another node (destination node) located on a different segment (inter-segment communication), the multi-port bridge 10 appropriately forwards the data packet to the destination node.
More particularly, the multi-port bridge 10 (FIG. 1) receives each data packet 40 (FIG. 2) and must determine whether the data packet 40 is for intra-segment communication or inter-segment communication, and if the data packet 40 is for inter-segment communication, the multi-port bridge 10 must determine to which port (destination port) the data packet 40 is to be directed based upon the destination address 42 contained in the data packet 40. This can be accomplished by utilizing a look-up table which associates the destination address 42 included in the packet 40 to a port of the multi-port bridge 10. Conventionally, the look-up table is constructed by executing a learning operation and a look-up operation for each received data packet 40. Thus, the learning operation is placed in the critical path of the packet and must also be completed before the packet can be directed to the appropriate to destination port. During the learning operation, the source address 43 from the data packet 40 is stored in the table in association with the identification of the source port. During the look-up operation, the destination address 42 is utilized to look-up data stored during the learning operation for a prior packet so as to identify the appropriate destination port for the packet 40.
Problems can arise, however, when the capabilities of the multi-port bridge 10 are exceeded by network demand. When data packets 40 are received by the multi-port bridge 10 at a rate that is higher than the rate at which the multi-port bridge 10 can appropriately perform a learning operation and a look-up operation for each packet 40 and, then, forward the packet, the multi-port bridge 10 becomes a source of network congestion. This problem is exacerbated as network users place increasing demands on the network.
Therefore, what is needed is improved technique for increasing the data packet handling capacity in a multi-port bridge for a local area network.
The invention is a statistical learning technique in a multi-port bridge for a local area network (LAN). In response to data packets received by the multi-port bridge, learning operations are performed for updating a look-up table in the multi-port bridge. The look-up table is utilized for identifying an appropriate destination port for the data packets by performing a look-up operation for each data packet. In accordance with the present invention, a learning operation is not performed for every packet received by the multi-port bridge. Rather, a learning operation is performed only in response to selected ones of the data packets. This minimizes the need to preoccupy the look-up table for performing learning operations and, thus, increases the availability of the look-up table for performing look-up operations.
A plurality of ports of the multi-port bridge are each coupled to a look-up bus. The look-up bus is coupled to the look-up table via a memory controller. Accordingly, look-up and learning operations for data packets received by a port of the multi-port bridge are performed via the look-up bus and the memory controller. The memory controller includes a look-up address queue and a learning address queue each of which are coupled to the look-up bus. In addition, a look-up controller is coupled to the look-up address queue, while a statistical learning controller is coupled to the learning address queue. A memory arbiter controls access to the look-up table.
When a data packet is received by a source port for the packet, the source port transfers the destination and source addresses for the packet via the look-up bus to the memory controller. The destination and source addresses for the packet are simultaneously stored in both the look-up address queue and in the learning address queue. When the look-up controller is available for performing a next look-up operation, the look-up controller requests permission to access the look-up table from the memory arbiter. Upon being granted permission, the look-up controller accesses the look-up table for determining whether the received packet is to be filtered, or if not filtered, to identify the appropriate destination port for the packet. The results of the look-up operation are then returned to the look-up bus where they are available to the source port and to the appropriate destination port for appropriately directing the packet through the multi-port bridge.
When the statistical learning controller is available for performing a next learning operation, the destination address next in the learning queue is transferred to the statistical learning controller. Based upon the destination address, the statistical learning controller determines whether the corresponding data packet is a broadcast packet or a uni-cast packet. If the packet is a broadcast or multi-cast packet, the statistical learning controller forwards a request to the memory arbiter for a learning operation. Upon being granted, the look-up table is updated. If the packet is a uni-cast packet, the statistical learning controller forwards a request to the memory arbiter for a learning operation only if (m) uni-cast packets have been received since a prior learning operation was performed for a uni-cast packet. In the preferred embodiment, (m) is sixteen. Accordingly, the look-up table is preferably updated in response to every broadcast and multi-cast packet and in response to every sixteenth uni-cast data packet.
In accordance with an aspect of the present invention, an apparatus for directing data packets through a multi-port bridge for a local area network (LAN) includes: table means for storing addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; look-up means coupled to the table means for identifying destination ports for each of a plurality of at least (m) uni-cast packets received by the multi-port bridge; and learning means coupled to the table means for updating the table means only in response to every (m)th uni-cast data packet of the plurality of at least (m) uni-cast data packets.
In accordance with another aspect of the present invention, an apparatus for directing data packets through a multi-port bridge for a local area network (LAN) includes: table means for storing addresses of nodes of the LAN in-association with an identification of a port of the multi-port bridge corresponding to each stored address; and learning means coupled to the table means for updating the table means once for every (m) uni-cast packets received by the multi-port bridge.
In accordance with yet another aspect of the present invention, a multi-port bridge for a local area network (LAN), the multi-port bridge comprising: a look-up table wherein the look-up table stores addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; and a statistical learning controller coupled to the look-up table wherein the statistical learning controller selectively updates the look-up table in response to a data packet received by the multi-port bridge based upon a destination address included in the data packet.
In accordance with still another aspect of the present invention, a method of statistically updating a look-up table in a multi-port bridge for a local area network (LAN), the method comprising steps of: receiving a data packet; determining whether the data packet is a uni-cast data packet; when the data packet is a uni-cast data packet, determining whether a predetermined number of uni-cast data packets have been received without having updated the look-up table in response; and when the predetermined number of uni-cast data packets have been received without having updated the look-up table in response, performing a step of updating the look-up table in response to the data packet.
In accordance with a further aspect of the present invention, a method of statistically updating a look-up table in a multi-port bridge for a local area network (LAN) includes steps of: receiving a data packet; and determining whether a predetermined period of time has elapsed since the multi-port bridge was last powered-on or reset, and when the predetermined period of time has not elapsed, performing a step of updating the look-up table in response to the data packet, and when the predetermined period of time has elapsed, performing steps of: determining whether the data packet is a uni-cast data packet; when the data packet is a uni-cast data packet, determining whether a predetermined number of uni-cast data packets have been received without having updated the look-up table in response; and when the predetermined number of uni-cast data packets have been received without having updated the look-up table in response, performing a step of updating the look-up table in response to the data packet.
In accordance with a still further aspect of the present invention, a multi-port bridge for interconnecting a plurality of segments of a local area network (LAN), the multi-port bridge comprising: a plurality of ports, each port for communicating with a corresponding segment of the LAN; a communication bus coupled to each of the plurality of ports; a look-up table coupled to the communication bus wherein the look-up table stores addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; a look-up controller coupled to the look-up table for identifying a destination port for each of a plurality of at least (m) uni-cast data packets received by the multi-port bridge; and a statistical learning controller coupled to the look-up table wherein the statistical learning controller updates the look-up table in response every (m)th uni-cast data packet received by the multi-port bridge and in response to every broadcast data packet received by the multi-port bridge.